package subjectlist;

public class L如何在不排序的情况下求数组中的中位数 {

    private static class 类快速排序{
        private static int pos=0;
        //以arr[low]为基准把数组分成两部分
        private static void partition(int arr[],int low,int high){
            int key=arr[low];
            while (low < high) {
                while (low < high && arr[high] > key) {
                    high--;
                }
                arr[low]=arr[high];
                while (low < high && arr[low] < key) {
                    low++;
                }
            }
            arr[low]=key;
            pos=low;
        }

        public static int getMid(int arr[]){
            int low=0;
            int n=arr.length;
            int high=n-1;
            int mid=(low+high)/2;
            while (true) {
                //以arr[low]为基准把数组分成两部分
                partition(arr,low,high);
                if (pos == mid) {
                    break;
                }else if(pos>mid){
                    high=pos-1;
                }else {
                    low=pos+1;
                }
            }
            //如果数组长度是奇数，中位数为中间的元素，否则就是中间两遏制
            return (n%2)!=0?arr[mid]:(arr[mid]+arr[mid+1])/2;
        }

        public static void main(String[] args) {
            int arr[]={7,5,3,1,11,9};
            System.out.println(getMid(arr));
        }
    }
}
